﻿// 301 石子合并.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <memory.h>


using namespace std;


/*

http://oj.daimayuan.top/course/5/problem/199

有 n堆石子排成一排，第 i堆石子有 ai颗，
 每次我们可以选择相邻的两堆石子合并，代价是两堆石子数目的和，现在我们要一直合并这些石子，
 使得最后只剩下一堆石子，问总代价最少是多少？

输入格式
第一行一个数字 n。

接下来一行 n个整数 a1,a2,…,an。

输出格式
一行一个整数，表示答案。

样例输入
3
1 2 3
样例输出
9
数据规模
对于所有数据，保证 1≤n,ai≤500。
*/

 
const int N = 510;

int dp[N][N];
int arr[N], preSum[N];
int n;

int dfs(int l, int r) {
	if (l == r) { dp[l][l] = 0; return 0; }
	int& res = dp[l][r];
	if (res != 0x3f3f3f3f) return res;
	for (int i = l + 1; i <= r; i++) {
		res = min(res, dfs(l,i-1) + dfs(i,r));
	}

	res += preSum[r] - preSum[l - 1];
	return res;
}



int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		preSum[i] = preSum[i - 1] + arr[i];
	}
	memset(dp, 0x3f, sizeof dp);
	cout << dfs(1, n) << endl;


	return 0;
}